package leetcode

// https://leetcode.cn/problems/number-of-islands/description/

// numIslands 计算给定二维字符数组中岛屿的数量。
// grid 代表一个由 '1'（陆地）和 '0'（水域）组成的二维网格。
// 返回岛屿的数量。
func numIslands(grid [][]byte) int {
	// columnNum 和 rowNum 分别代表网格的行数和列数。
	columnNum := len(grid)
	rowNum := len(grid[0])

	// 创建一个新的 IslandUnionFind 实例，用于处理岛屿的并查集。
	islandUnionFind := NewIslandUnionFind(&grid, columnNum, rowNum)

	// 遍历整个网格，对每个单元格进行处理。
	for i := 0; i < columnNum; i++ {
		for j := 0; j < rowNum; j++ {
			// 如果当前单元格是陆地，则检查其上方和左方是否也是陆地。
			if grid[i][j] == '1' {
				// 如果当前陆地上方也有陆地，则将它们合并到同一个集合中。
				if i > 0 && grid[i-1][j] == '1' {
					islandUnionFind.Union(Index(i-1, j, rowNum), Index(i, j, rowNum))
				}

				// 如果当前陆地左方也有陆地，则将它们合并到同一个集合中。
				if j > 0 && grid[i][j-1] == '1' {
					islandUnionFind.Union(Index(i, j-1, rowNum), Index(i, j, rowNum))
				}
			}
		}
	}

	// 返回并查集中剩余的集合数量，即岛屿的数量。
	return islandUnionFind.setNum
}

// IslandUnionFind 实现了并查集数据结构，用于处理岛屿连接问题。
type IslandUnionFind struct {
	parent []int // 记录每个元素的父节点。
	size   []int // 记录每个集合的大小。
	help   []int // 辅助数组，用于路径压缩。
	setNum int   // 当前并查集中集合的数量，即岛屿的数量。
}

// NewIslandUnionFind 创建并初始化一个新的 IslandUnionFind 实例。
// grid 是待处理的二维网格，columnNum 和 rowNum 分别是网格的行数和列数。
// 返回初始化后的 IslandUnionFind 实例。
func NewIslandUnionFind(grid *[][]byte, columnNum, rowNum int) *IslandUnionFind {
	// n 是网格的总单元格数。
	n := columnNum * rowNum
	// 初始化并查集的数据结构。
	parent := make([]int, n)
	size := make([]int, n)
	help := make([]int, n)
	setNum := 0

	// 遍历网格，对每个单元格进行初始化。
	for i := 0; i < columnNum; i++ {
		for j := 0; j < rowNum; j++ {
			// 如果当前单元格是陆地，则初始化对应的并查集元素。
			if (*grid)[i][j] == '1' {
				index := Index(i, j, rowNum)
				parent[index] = index
				size[index] = 1
				setNum++
			}
		}
	}

	// 返回初始化后的 IslandUnionFind 实例。
	return &IslandUnionFind{parent, size, help, setNum}
}

// Union 合并两个集合。
// islandIndex1 和 islandIndex2 是两个元素的索引，它们分别属于不同的集合。
func (uf *IslandUnionFind) Union(islandIndex1, islandIndex2 int) {
	// 找到两个元素所在集合的根节点。
	root1 := uf.Find(islandIndex1)
	root2 := uf.Find(islandIndex2)

	// 如果两个根节点不同，说明属于不同的集合，需要进行合并。
	if root1 != root2 {
		// 根据集合的大小进行合并，以保持并查集的平衡。
		if uf.size[root1] >= uf.size[root2] {
			uf.parent[root2] = root1
			uf.size[root1] += uf.size[root2]
		} else {
			uf.parent[root1] = root2
			uf.size[root2] += uf.size[root1]
		}
		// 合并后集合数量减少。
		uf.setNum--
	}
}

// Find 查找元素所在集合的根节点，并进行路径压缩。
func (uf *IslandUnionFind) Find(islandIndex int) int {
	helpIndex := 0
	// 在查找根节点的过程中，进行路径压缩。
	for islandIndex != uf.parent[islandIndex] {
		uf.help[helpIndex] = islandIndex
		helpIndex++

		islandIndex = uf.parent[islandIndex]
	}

	// 将查找路径上的所有节点直接连接到根节点，优化查询效率。
	for helpIndex > 0 {
		helpIndex--
		onTheWayIndex := uf.help[helpIndex]
		uf.parent[onTheWayIndex] = islandIndex
	}

	// 返回元素所在集合的根节点。
	return islandIndex
}

// Index 根据行列索引计算一维索引。
func Index(i, j, rowNum int) int {
	return i*rowNum + j
}
